package com.sort;


import java.util.Arrays;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/4/27 11:03
 * @description 冒泡排序
 */
public class BubbleSort {

    //两个数异或 相同为0  不同为1

    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 0, 1, 8, 7, 12};

//        bubble_confirm_right_range_D(arr, arr.length - 1);
//        bubble(arr);
        bubble_confirm_right_range(arr);
        System.out.println(Arrays.toString(arr));
    }

    //每次把最大的那个元素顶到数组的最后一个 最后一个每一次完成后需要-1
    public static void bubble(int[] arr) {
        int end = arr.length - 1;
        while (end != 0) {
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    int t = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = t;
                }
            }
            end--;
        }
    }

    /*
    优化 确定一个右边界来减少比较次数
    以3，2，1，4，5 为例
    第一轮结束后记录的x 就是右边界5
     */
    public static void bubble_confirm_right_range_D(int[] arr, int j) {
        if (j == 0) return;
        int x = 0;
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                int t = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
                x = i;
            }
        }
        bubble_confirm_right_range_D(arr, x);
    }

    //优化版本 非递归实现
    public static void bubble_confirm_right_range(int[] arr) {
        int j = arr.length - 1;
        do {
            int x = 0;
            for (int i = 0; i < j; i++) {
                if (arr[i] > arr[i + 1]) {
                    int t = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = t;
                    x = i;
                }
            }
            j = x;
        } while (j != 0);
    }


}
